package ch10;

public class Ch10_6 {
	class Wrapper {
		private int a;
		private int b;
		public Wrapper(int a, int b) {
			this.a = a;
			this.b = b;
		}
		
		public String toString() {
			return "(" + a + ", " + b + ")";
		}
	}
	
	public Wrapper find(int[][] tab, int key) {
		int cl = 0, cr = tab[0].length - 1;
		int rt = 0, rb = tab.length - 1;
		
		while (cl < cr && rt < rb) {
			int cm = (cl + cr) / 2;
			if (cm == cl) {
				break;
			}
			int rm = (rt + rb) / 2;
			if (rm == rt) {
				break;
			}
			if (tab[rm][cm] == key) {
				return new Wrapper(rm, cm);
			} else if (tab[rm][cm] > key) {
				cr = cm;
				rb = rm;
			} else {
				cl = cm;
				rt = rm;
			}
		}
		
		for (int i = rt; i <= rb; i++) {
			for (int j = cl; j <= cr; j++) {
				if (tab[i][j] == key) {
					return new Wrapper(i, j);
				}
			}
		}
		return new Wrapper(-1, -1);
	}
	
	static void printTab(int[][] tab) {
		for (int i = 0; i < tab[0].length; i++) {
			System.out.print("\t" + i);
		}
		System.out.println();
		for (int i = 0; i < tab.length; i++) {
			System.out.print(i + ":");
			for (int j = 0; j < tab[i].length; j++) {
				System.out.print("\t" + tab[i][j]);
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Ch10_6 test = new Ch10_6();
		int row = 5, col = 10;
		int[][] tab = new int[row][col];
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				tab[i][j] = i * tab[i].length + j;
			}
		}
		printTab(tab);
		
		int key = 15;
		Wrapper result = test.find(tab, key);
		System.out.println(result);
	}
}
